/*
Date:				2017-2-07
Author:				GangTimes
Address:			JSB-0210-220
dependent file:  	iterator.h head.h

The file is a kind of implemation with vector.

*/


#ifndef VECTOR_H_
#define VECTOR_H_
#include<iostream>
template<typename T>
class vector;

template<typename T>
ostream & operator<<(ostream&, const vector<T> &);

template<typename T>
istream & operator>>(istream&, const vector<T> &);

template<typename T>
class vector
{
public:
	typedef T				value_type;
	typedef value_type*		iterator;
	typedef value_type*		pointer;
	typedef value_type&		reference;
	typedef size_t			size_type;
	typedef ptrdiff_t		difference_type;

private:
	T* arr;
	T* lrr;
	T* crr;
	int cap;
	int len;

	void shrink();
	void expand();

public:
	vector();
	vector(int, T);
	vector(const vector &);
	vector(int);
	vector(const iterator, const iterator);
	vector& operator=(const vector &);
	void clear();
	~vector();
	void push_head(T);
	void push_back(T);

	void insert(int,T);
	void insert(int, int, T);
	void insert(int, iterator, iterator);
	                                                                                                
	void deleteFront();

	void pop_back();
	void pop_front();
	value_type erase(int);
	value_type erase(iterator, iterator);

	int size();
	int capacity();
	bool isempty();

	reference operator[](int);
	reference at(int);
	reference front();
	reference back();

	
	iterator begin();
	iterator end();
	iterator begin()const;
	iterator end()const;

	iterator rbegin();
	iterator rend();
	iterator rbegin()const;
	iterator rend()const;
	//函数模板参数不添加 再gcc中会有警告 再vs能够运行
	friend ostream & operator<< <T>(ostream&,const vector<T> &);
	friend istream & operator>> <T>(istream&,const vector<T> &);

};

template<typename T>
vector<T>::vector()
:cap(4), len(0)
{
	arr = (T*)malloc(cap*sizeof(T));
	lrr = arr + len;
	crr = arr + cap;
}

template<typename T>
vector<T>::vector(int num, T elem)
: cap(num), len(num)
{
	arr = (T*)malloc(cap*sizeof(T));
	lrr = arr + len;
	crr = arr + cap;
	for (auto temp = arr; temp != lrr; ++temp)
	{
		(*temp) = elem;
	}
}

template<typename T>
vector<T>::vector(const vector & vec)
:cap(vec.cap), len(vec.len)
{
	arr = (T*)malloc(cap*sizeof(T));
	lrr = arr + len;
	crr = arr + cap;
	for (int i = 0; i < len; ++i)
	{
		*(arr + i) = (*(vec.arr + i));
	}
}

template<typename T>
vector<T>::vector(int num)
:cap(num), len(0)
{
	arr = (T*)malloc(cap*sizeof(T));
	lrr = arr + len;
	crr = arr + cap;
}

template<typename T>
vector<T>::vector(const iterator first,const iterator last)
:vector()
{
	for (auto temp = first; temp != last; ++temp)
	{
		push_back(*temp);
	}
}

template<typename T>
vector<T>& vector<T>::operator = (const vector & vec)
{
	vector<T> * temp = new vector<T>(*this);

	cap = vec.cap;
	len = vec.len;
	arr = (T*)malloc(cap*sizeof(T));
	lrr = arr + len;
	crr = arr + cap;

	for (int i = 0; i < len; ++i)
	{
		*(arr + i) = (*(vec.arr + i));
	}

	delete temp;

	return *this;
}

template<typename T>
vector<T>::~vector()
{
	clear();
	crr = arr;
	cap = 0;
	delete arr;
	arr = nullptr;
	lrr = nullptr;
	crr = nullptr;
}

template<typename T>
void vector<T>::clear()
{
	lrr = arr;
	len = 0;
}

template<typename T>
void vector<T>::push_head(T elem)
{
	expand();
	for (auto temp = lrr; temp !=arr; --temp)
	{
		(*temp) = (*(temp - 1));
	}
	*arr = elem;
	++lrr;
	len += 1;
}

template<typename T>
void vector<T>::push_back(T elem)
{
	expand();
	*lrr = elem;
	++lrr;
	len += 1;
}

template<typename T>
void vector<T>::insert(int index, T elem)
{
	expand();
	for (auto temp = lrr; temp != (arr + index); --temp)
	{
		(*temp) = (*(temp - 1));
	}
	(*(arr + index)) = elem;
	++lrr;
	len += 1;
}

template<typename T>
void vector<T>::insert(int index,int num, T elem)
{
	expand();
	auto templrr = lrr;
	lrr += num;
	for (int i = 0; i < len-index; ++i)
	{
		(*(lrr-1-i)) = (*(templrr - i-1));

	}
	for (int i = 0; i < num; ++i)
	{
		(*(arr + index+i)) = elem;
	}

	len += num;
}

template<typename T>
void vector<T>::insert(int index, const iterator first, const iterator last)
{
	expand();
	auto templrr = lrr;
	lrr += (last-first);
	for (int i = 0; i < len - index; ++i)
	{
		(*(lrr - 1 - i)) = (*(templrr - i - 1));

	}
	
	int num = 0;
	
	for (auto temp = first; temp!=last; ++temp)
	{
		(*(arr + index + num)) = *temp;
		++num;
	}
	len += num;
}


template<typename T>
void vector<T>::expand()
{
	if (lrr < crr)
		return;
	
	cap *= 2;
	T* _arr = (T*)malloc(cap*sizeof(T));
	T* _lrr = _arr;
	T* _crr = _arr + cap;

	for (auto temp = arr; temp != lrr; ++temp)
	{
		(*(_lrr++)) = (*temp);
	}

	arr = _arr;
	lrr = _lrr;
	crr = _crr;
}

template<typename T>
void vector<T>::shrink()
{
	if (len > (cap >> 2))
		return;
	
	cap = cap >> 1;
	crr = arr + cap;
}


template<typename T>
void vector<T>::pop_back()
{
	if (lrr == arr)
	{
		cout << "the vector don't have any element" << endl;
		return;
	}
	
	shrink();
	len -= 1;
	lrr -= 1;
}
template<typename T>
void vector<T>::pop_front()
{
	if (lrr == arr)
	{
		cout << "the vector don't have any element" << endl;
		return;
	}
	
	shrink();
	len -= 1;
	arr += 1;
}
template<typename T>
typename vector<T>::value_type 
vector<T>::erase(int index)
{
	if (index<0 || index>len - 1)
	{
		cout << "the index is illegal" << endl;
		return 0;
	}
	
	shrink();
	
	for (auto temp = arr + index + 1; temp != lrr; ++temp)
	{
		(*(temp - 1)) = (*temp);
	}
	
	lrr -= 1;
	len -= 1;
	return *(arr + index);
}

template<typename T>
typename vector<T>::value_type
vector<T>::erase(iterator first,iterator last)
{
	shrink();
	int num = 0;
	
	for (auto temp = last; temp != lrr;++temp)
	{
		(*(first+num)) = (*temp);
		++num;
	}
	
	lrr -= (last - first);
	len -= num;
	
	return *first;
}
template<typename T>
int vector<T>::size()
{
	return len;
}

template<typename T>
int vector<T>::capacity()
{
	return cap;
}

template<typename T>
bool vector<T>::isempty()
{
	return arr==lrr;
}

template<typename T>
typename vector<T>::reference
vector<T>::operator[](int index)
{
	return *(arr + index);
}

template<typename T>
typename vector<T>::reference
vector<T>::at(int index)
{
	if (index<0 || index>len-1)
	{
		throw("the index is illegal");
	}
		
	return *(arr + index);
}

template<typename T>
typename vector<T>::reference
vector<T>::front()
{
	return *arr;
}

template<typename T>
typename vector<T>::reference
vector<T>::back()
{
	return *(lrr-1);
}


template<typename T>
ostream& operator<<(ostream& os,vector<T> & vec)
{
	for (auto temp = vec.begin(); temp != vec.end(); ++temp)
	{
		os << *temp << endl;
	}
	return os;
}
template<typename T>
istream& operator>>(istream& is, vector<T> & vec)
{
	cout << "please input the element,click eof exit input" << endl;
	char stop;
	T d;
	
	while (true)
	{
		is >> d;
		vec.push_back(d);
		
		if ((stop = is.get()) == '\n')
			break;
	}
	
	return is;
}

template<typename T>
typename vector<T>::iterator
vector<T>::begin()
{
	return arr;
}

template<typename T>
typename vector<T>::iterator
vector<T>::end()
{
	return lrr;
}

template<typename T>
typename vector<T>::iterator
vector<T>::begin()const
{
	return arr;
}

template<typename T>
typename vector<T>::iterator
vector<T>::end()const
{
	return lrr;
}

template<typename T>
typename vector<T>::iterator
vector<T>::rbegin()
{
	return lrr-1;
}

template<typename T>
typename vector<T>::iterator
vector<T>::rend()
{
	return arr-1;
}

template<typename T>
typename vector<T>::iterator
vector<T>::rbegin()const
{
	return lrr - 1;
}

template<typename T>
typename vector<T>::iterator
vector<T>::rend()const
{
	return arr - 1;
}
#endif